package BinaryTree;
/*
* * 二叉树的最近公共祖先
 * 思路：
 * 三种情况：
 * 1、p q 一个在左子树 一个在右子树 那么当前节点即是最近公共祖先
 * 2、p q 都在左子树
 * 3、p q 都在右子树
 *
 * 思路:
 * p 和 qq 在 rootroot 的子树中，且分列 rootroot 的 异侧（即分别在左、右子树中）；
p = rootp=root ，且 qq 在 rootroot 的左或右子树中；
q = rootq=root ，且 pp 在 rootroot 的左或右子树中；

*
* */
public class LowestCommonAncestor236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p){
            return p;
        }
        if(root==q){
            return q;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        return root;
    }
}
